\documentclass[twoside]{article}
\usepackage [ italian  ]{ babel }
\usepackage{amsmath,amssymb,amsthm,graphicx,bm, color, tikz}
\usepackage{epsfig}
\usepackage{epstopdf}
\DeclareGraphicsExtensions{.png,.pdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\usepackage[authoryear]{natbib}

\input{stat-macros}

\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}


% Local Macros Put your favorite macros here that don't appear in
% stat-macros.tex.  We can eventually incorporate them into
% stat-macros.tex if they're of general use.
 \newenvironment{mylisting}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}

\newenvironment{code}{\begin{verse}
	\tt $\{$ \\
}{$\}$ \\
 \end{verse}}

\begin{document}

\lezione{ Inferenza esatta su DAG per enumerazone completa.}{Prof. Giuseppe Boccignone}{Alberto Massa}{24 Aprile 2010}

\section{Introduzione}

Il compito principale di ogni motore di inferenza e' trovare la distribuzione di probabilita' di variabili nascoste dati alcuni eventi osservati e un graphical model che le correla. \\
Seguendo l'approccio bayesiano si puo' fare inferenza su variabili nascoste, sui parametri e sul modello, perche' sono tutte considerate variabili aleatorie. \\
In questa lezione vedremo il metodo di inferenza esatta sulle variabili nascoste per enumerazione completa. E' un metodo di brute-force, concettualmente semplice ma computazionalmente molto oneroso, che ci spingera' ad adottare, nelle prossime lezioni, metodologie approssimate più convenienti come, per esempio, tecniche Montecarlo.

\section{Enumerazione completa}
Riprendiamo il problema del prato di Bob e Alice:

\textit{Alice si sveglia la mattina e trova il prato del giardino bagnato, vuole capire se  ́ bagnato perch ́  ́ piovuto
o perch ́ si  ́ dimenticata l’irrigatore aperto durante la notte. Osserva i prato di Bob, il suo vicino, anche
questo e bagnato e si chiede se sia dovuto alla pioggia o al fatto che anche Bob si sia dimenticato l'’irrigatore
aperto.}

Possiamo esprimere questo problema con il seguento graphical model: \\

\begin{center}
\includegraphics[scale=0.6]{Vincoli_fisici.png}
\end{center}

\begin{table}[h]
\centerline{
    \begin{tabular}{|c|c|}
        \hline
        \textbf P & $P(P)$ \\
        \hline
        1 & 0.2 \\
        0 & 0.8 \\
        \hline
    \end{tabular}}
\caption{Probabilita' che piova (P=1) o che non piova (P=0).}

\centerline{
    \begin{tabular}{|c|c|}
        \hline
        \textbf I & $P(I)$ \\
        \hline
		1 & 0.1\\
		0 & 0.9\\
        \hline
    \end{tabular}}
\caption{Probabilita' che l'irrigatore sia acceso (I=1) o spento (I=0).}

\centerline{
    \begin{tabular}{|c|c|}
        \hline
        \textbf P & $P(B=1|P)$ \\
        \hline
		1 & 1 \\
		0 & 0.2 \\
        \hline
    \end{tabular}}
\caption{Probabilita' che il prato di Bob sia bagnato posto che sia piovuto o no.}

\centerline{
    \begin{tabular}{|c|c|c|}
        \hline
        \textbf P & I & $P(A=1|P,I)$ \\
        \hline
		1 & 0 & 1 \\
		1 & 1 & 1 \\
		0 & 0 & 0 \\
		0 & 1 & 0.9 \\
        \hline
    \end{tabular}}
\caption{Probabilita' che il prato di Alice sia bagnato posto P e I.}
\end{table}

Congiunta (\textit{Joint probability}):
\begin{equation}
\label{eq:mu}
P(P,I,A,B) = P(I)P(P)P(A|P,I)P(B|P).
\end{equation}
\\ \\
Osservazioni:
\begin{itemize}

\item La congiunta e', concettualmente, il modo piu' semplice per rappresentare relazioni fra variabili aleatorie. La congiunta (modello globale) e' espressa tramite le tabelle di probabilita' condizionata e marginalizzazioni (modelli locali ad ogni nodo del grafo).
\item Ha un grosso inconveniente: in linea teorica in una congiunta ogni variabile e' direttamente collegata ad ogni altra varibaile. Cioe'.. complessita' esponenziale! Se ho \textit{m} variabili (binarie, cioe' che prendono valore su un insieme di due elementi) ho bisogno di $2^m$ passi per calcolare tutte le dipendenze date dalla congiunta. 
\footnote{\textit{ecco perche' la teoria delle probabilita' non ha giocato un ruolo di spicco nel campo delle AI prima del 1980}}
\item Con l'aiuto del graphical model (connubio fra la teoria dei grafi e la teoria delle probabilita') aggiungiamo conoscienza extra-domain, \textit{a different kind of knowledge than numerical probabilities, it needed an understanding of causation} (Andrew W. Moore). In questo modo siamo in grado di ridurre il grado computazionale limitando le dipendenze fra le variabili aleatorie. I graphical models (o reti bayesiane) rappresentano un insieme di dipendenze.
\item Ora non ci serve piu' una tabella con il numero di righe esponenziale al numero di variabili, ma esponenziale al numero di nodi padre nel graphical model.
\item I valori di queste tabelle derivano da un apprendimento di qualche tipo. E questo e' la base delle nostre conoscienze sul mondo. Rappresenta il nostro modello.
\item I parametri sono contenuti nelle PCT (\textit{Probability Conditional Table}).
\item Il graphical model rappresenta come le conoscenze che ho sul problema sono correlate.
\item I nodi del graphical model costituiscono le variabili, che possono essere aleatorie (da inferire) oppure osservate. 
\item Ricordiamo che tutte le variabili in questo esempio assumono valori dall'insieme discreto $\lbrace {0,1} \rbrace$.
Le tabelle PCT e il graphical model sono sufficenti per fare inferenza. 

\end{itemize}
Esempio 1:\\
Osservo il prato di Alice (il nodo A) e voglio sapere se l'irrigatore e' rimasto acceso, 
ovvero inferire lo stato dell'irrigatore. \\
Come si scrive matematicamente? Con la seguente query:\\
$P(I=1|A=1)$ \\
E si legge: la probabilita' condizionata di I (che l'irrigatore sia acceso) 
dato A (che il prato di Alice e' bagnato). \\

$$P(I=1|A=1)$$
\begin{flushright}
(query di partenza) \\
\end{flushright}
$$ = \frac{P(I=1,A=1)}{P(A=1)}$$
\begin{flushright}
(definizione di probabilita' condizionata) \\
\end{flushright}
$$ = \frac{ \sum_{P,B}{P(P, B, I=1, A=1 )} }{\sum_{P,I,B}{P(P, I, B, A=1}}$$
\begin{flushright}
(marginalizzazione ricavata dai legami di condizionamento dalla figura a pagina 1.) \\
\end{flushright}
$$ = \frac{ \sum_{P,B}{P(P) P(B|P) P(I=1) P(A=1|I=1, P) } }{ \dots }$$
\begin{flushright}
(sviluppo della congiunta sulle variabili aleatorie e su quelle osservate) \\
\end{flushright}
$$ = \frac{ \sum_{P}{P(P) P(I=1) P(I=1|A=1, P)} }{ \dots }$$
\begin{flushright}
(elimino $P(B|P)$ perche' $\sum_{B}{P(P|B)}$ con $B \in \lbrace 0,1 \rbrace$ \\
e' uguale a $P(B=0|P)+P(B=1|P) = 1)$
\end{flushright}
Bisogna sviluppare tutte le sommatorie, sia per in nominatore sia per il denominatore. Ecco perche' questa tecnica si chiama \textbf{inferenza per enumerazione completa}. \\
Una volta che ho sviluppato tutte le sommatorie posso prendere i valori dalle tabelle e ottenere il risultato. \\
Proseguendo i calcoli si ottiene:\\
$$P(I=1 | A=1) = \frac{0.092}{0.272} = 0.3382$$
Che e' la probabilita' che l'irrigatore di Alice sia stato acceso dato che il suo prato e' bagnato. 
\\ \\
Considerazioni:
\begin{itemize}
\item Inizialmente $P(I=1)$ era 0.1. Osservando che il prato e' bagnato.. le probabilita' aumentano. E' un concetto intuitivo, ma e' stato risolto in maniera chiusa, \textit{Bayesian probability theory is sometimes called 'common sense amplified', cit. McKey cap. 21}.
\item Il calcolo e' strettamente connesso al modello concettuale del problema.
\item Con il graphical model abbiamo ridotto le dipendenze fra le variabili della congiunta. Ma la complessita' di sommatorie annidate rimane comunque esponenziale (l'inferenza per enumerazione completa nelle reti bayesiane è comunque un problema NP-completo), e le variabili aleatorie possono non essere discrete ma essere funzioni di probabilita' polinomiale. E' per questo che nella pratica spesso si passa a tecniche approssimate come simulazioni stocastiche di Montecarlo.
\item Il calcolo del denominatore: e' qui che esce il grado computazionale (perche' e' la parte dell'equazione con il grado piu' alto). Il denominatore corrisponde alla funzione di partizione della meccanica quantistica, e serve alla normalizzazione.
\end{itemize}

\section{Indipendenza condizionale su graphical model}
\subsection{Riprendiamo l'esempio Bob-Alice-Prato bagnato}
Esempio 2: \\
Osservo anche B. Osservo il prato di Bob e osservo il prato di Alice e voglio inferire sullo stato dell'irrigatore. Che probabilita' ci sono che sia acceso o spento? 
\\
Query:
$$P(I=1|A=1,B=1)$$
$$ = \frac{P(I=1, A=1, B=1}{P(A=1, P=1)}$$
$$ = \frac{\sum_{P}{P(P, I=1, A=1, B=1}}{\sum_{P,I}{P(I, P, A=1, B=1)}}$$
\begin{flushright}
(Sostituisco la definizione di congiunta, e cosi' via, come nell'Esempio 1) \\
\end{flushright}
$$\dots$$
$$= \frac{0.344}{0.2144} \approx 0.16 $$

Probabilita' a priori: $P(I)=0.1$ \\
Evidenza, osservo Alice: $P(I|A)=0.3$ \\
Evidenza, osservo anche Bob: $P(I|A,B) = 0.16$\\
\\
Cosa e' successo? Stabiliamo delle dipendenze condizionali e non ci aspettiamo che un nodo nel DAG condizioni un nodo lontano. \\
Questo e' chiamato il fenomeno di \textbf{explaning away}. Una nuova osservazione ha spazzato via un'ipotesi precedente, indipendenza condizionale.\\

\subsection{Tail-to-tail: cause comuni}
\begin{figure}
\begin{center}

\includegraphics[scale=0.2]{enumerazioni_cause_comuni.png} 
\caption{Cause comuni}
\end{center}
\end{figure}

$$a \bot b | c$$
\textit{a} e \textit{b} dipendono da \textit{c}, e non il contrario. \\
Congiunta:
$$  P(a,b,c) = p(c) p(a|c) p(b|c)  $$
Query: inferire \textit{a} e \textit{b}. Che relazione c'e' fra questi due nodi? 
\begin{itemize}
\item[1]
Non osservo \textit{c}. \\
Marginalizzo a destra e a sinistra.
$$ \sum_c{p(a,b,c)} $$
\begin{flushright}
(Definizione di marginalizzazione)
\end{flushright}
$$ p(a,b) = \sum_c{p(c)p(a|c)p(b|c)} $$
\begin{flushright}
(Marginalizzazione secondo il graphical mode)
\end{flushright}
$$ \ne p(a)p(b)$$
\begin{flushright}
(Definizione di probabilita' congiunta di variabili indipendenti)
\end{flushright}
Svolgendo i calcoli abbiamo trovato che se \textit{c} non e' osservata non vale l'indipendenza.
\item[2] Il nodo \textit{c} e' osservato, posso condizionare su \textit{c}:
$$ p(c,b|c) $$
$$ = \frac{p(a,b,c)}{p(c)}$$
$$ =\frac{p(a|c)p(b|c)p(c)}{p(c)} $$
\begin{flushright}
(Regola di Bayes)
\end{flushright}
$$ = p(a|c)p(b|c) $$
Abbiamo ottenuto la definizione di indipendenza condizionale!
\end{itemize}
L'osservazione di \textit{c}.. blocca. Mentre nel caso 1 non si ottiene l'indipendenza, nel secondo caso si:
il cammino da \textit{a} a \textit{b} viene interrotto. E' come se osservando venisse messo un muro e la "palla di Bayes" non passa ma ci rimbalza sopra. Questo fenomeno e' detto infatti \textbf{bayes-ball}\footnote{\textit{Vedi l'articolo: “Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams)”, Ross D. Shachter, per un'accurata spiegazione dell'algoritmo Bayes-ball di visita ai graphical model. }}.


\subsection{Head-to-tail: fenomeni temporali}
\begin{figure}
\begin{center}

\includegraphics[scale=0.2]{enumerazioni_catena.png} 
\caption{Catena temporale}
\end{center}
\end{figure}
Altra tipologia, a catena, utile per modellare fenomeni temporali come le catene di Markov. Per esempio per modella andamenti vocali o la dinamica del sorriso. Dati punti fiduciali sul labbro e una catena per ognuno di essi la probabilita' che ci sia un sorriso e' la probabilita' congiunta di queste quattro catene.\\
Congiunta:
$$ p(a,b,c) = \sum_c{p(a)p(b|a)p(b|c)}$$
Che ricorda molto la definizione di un modello di Markov:
$$ P(x_{t+1} | x_0, x_1, \dots, x_{t-1}) = p(x_{t+1}|x{t}) $$
\begin{itemize}

\item[1] \textit{c} non e' osservato.
$$ p(a,b) = p(a) \sum_c{p(b|a)p(c|b)} $$
Ma \textit{c} compare sia come variabile condizionata sia come variabile condizionante, definizione di marginalita'.
$$ = p(a)p(b|a) $$
$$ \ne p(a)p(b)$$
Se non sto osservando gli stati non c'e' indipendenza condizionale, la palla di Bayes non ha ostacoli, parte da \textit{a} e arriva a \textit{c}. Questo significa che la definizione di markovianita' va presa \textit{cum grano salis} se non si osservano variabili.
\item[2] Osservo \textit{b}.
$$ p(a,b|c) = $$
$$ = \frac{p(a,b,c)}{p(c)}$$
$$ = \frac{p(a)p(c|a ????? )p(b|c}{p(c)}$$
\begin{flushright}
(Regola di Bayes)
\end{flushright}
$$ = p(a|c)p(b|c)$$
Quando osservo in mezzo alla catena blocco il cammino, non ho dipendenza condizionale.
Il futuro e il passato sono cond. indipendenti dato il presente, questa regola è nota come \textbf{assunzione di Markov}.

\end{itemize}

\subsection{Head-to-head: effetti comuni}

\begin{figure}
\begin{center}
\includegraphics[scale=0.2]{enumerazioni_effetti_comuni.png} 
\caption{Effetti comuni}
\end{center}
\end{figure}

$$ p(a,b,c) = p(a)p(b)p(c|a,b)$$
\begin{itemize}

\item[1] Il nodo \textit{c} non e' osservato.\\
Marginalizzo su tutti i casi di \textit{c}:
$$ = \sum_c{p(a)p(b)p(c|a,b)}$$
$$ = p(a)p(b)\sum_c{p(c|a,b)}$$
\begin{flushright}
(\textit{c} e' solo nell'ultimo termine)
\end{flushright}
$$ = p(a)p(b) $$
\begin{flushright}
($\sum_c{p(c|a,b)}$ e' uguale a 1.)
\end{flushright}
Definizione di indipendenza. In questo caso \textit{c} non osservato.. blocca il cammino!\\
$a \bot b$
\textit{a} e' condizionalmente indipendente da \textit{b} se \textit{c} non e' osservato
\item[2] Condiziono su \textit{c}:
$$ = \frac{p(a,b,c)}{p(c)} = p(a,b|c)$$
$$ = \frac{p(a)p(b)p(c|a,b)}{p(c)}$$
$$ p(a|c)p(b|c$$
Ancora, definizione di indipendenza.\\
Questa configurazione topologica (e in altre simili) non si comporta come le altre!
E' quello che e' successo nell'esempio della pioggia.
\end{itemize}

\begin{center}

\includegraphics[scale=0.2]{enumerazioni_effetti_comuni2.png} 
\end{center}

Dietro a questi esempi sta il concetto di \textbf{D-separation}.\\
Posso prendere un grafo arbitrario, e se riesco a configurare un cammino da un nodo ad un altro allora i due nodi non sono d-separati. Se c'e' un taglio dato da nodi osservati si dicono d-separati.


\section{Conclusioni}
\begin{figure}
\begin{center}
\includegraphics[scale=0.2]{enumerazioni_contatore_geiger.png} 
\caption{Contatore Geiger}
\end{center}
\end{figure}
Problema della statistica classica: ho un insieme di variabili aleatorie indipendenti e identicamente distribuite (i.i.d. significa che sono indipendenti e che hanno una uguale distribuzione, per esempio, 3 gaussiane).\\
Supponiamo di avere un contatore Geiger che registra emissioni radioattive nel tempo e ne fa un istogramma. C'e' una buona probabilita' che segua la distribuzione di Poisson.\\
\footnote{\textit{La distribuzione di Poisson modella eventi rari introdotta da Siméon-Denis Poisson nel 1838 nel suo articolo "Recherches sur la probabilité des jugements en matière criminelle et en matière civile". Serve per modellare, fra le altre cose, l'arrivo di macchine ad un semaforo in alcune condizioni di traffico automobilistico o l'arrivo di processi nello scheduler di un sistema operativo.}}
I dati sono identicamente distribuiti (stessa fonte) e indipendenti. \\
La congiunta e': $ p(x_1, x_2, \dots, x_n) = \prod_{i=1}{p(x_i)}$ (si usa la produttoria perche', appunto, sono indipendenti).\\
Cosa vuol dire?\\
In statistica classica faccio assunzioni, che non sono mai esplicite.
$$ p(x_i = k) = \frac{\lambda^k e}{k!} $$
dove $\lambda$ e' un numero da stimare..\\
Seguendo l'approccio bayesiano dobbiamo esplicitare i parametri come variabili aleatorie:
$$ p(x_i = k | \lambda) $$
Rappresentando il modello grafico:\\
E' un grafo tail-to-tail.\\
Cosa vuol dire che le x sono statisticamente indipendenti?\\
Se $\lambda$ e' aleatoria, non osservata, non sono indipendenti. La statistica classica ha ragione con la produttoria solo se $\lambda$ e' osservata, perche' da la condizione a priori per scontata. \\
In realta' se non osservo $\lambda$:
$$ p(x_1, \dots, x_n) = \int_{\lambda}{p(x_1, \dots, x_n, \lambda)} d\lambda $$
Sicuramente sono identicamente distribuite, ma non indipendenti!
\\

\section{Bibliografia}
\begin{itemize}
\item
Information Theory, Inference, and Learning Algorithms, David J.C. MacKay, Cambridge University Press, 2003 \\
\item
Statistical data mining tutorial, Andrew Moore, http://www.autonlab.org/tutorials/ \\
\item
Video-lecture, Probability, Information Theory and Bayesian Inference, Joaquin Quiñonero Candela, Max Planck Institute for Biological Cybernetics, 2007.
\end{itemize}

\bibliographystyle{apalike}
\bibliography{bibliografia}

\end{document}



